home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / filesyst / dosfs / dmsdosfs.000 / dmsdosfs / dmsdosfs-0.6.9b / dmsdos_alloc.c < prev    next >
C/C++ Source or Header  |  1996-07-29  |  16KB  |  557 lines
  1. /* 
  2. linux/fs/dmsdos/dmsdos_alloc.c
  3.  
  4. DMSDOS filesystem: cluster allocation functions
  5.  
  6. ******************************************************************************
  7. DMSDOS (Doublespace/Drivespace compressed MSDOS filesystem) for Linux
  8. written 1995,1996 by Frank Gockel
  9.  
  10.     (C) Copyright 1995,1996 by Frank Gockel
  11.  
  12. Some code of the dmsdos filesystem has been copied from the msdos filesystem
  13. so there are the following additional copyrights:
  14.  
  15.     (C) Copyright 1992,1993 by Werner Almesberger (msdos filesystem)
  16.     (C) Copyright 1994,1995 by Jacques Gelinas (mmap code)
  17.     (C) Copyright 1992-1995 by Linus Torvalds
  18.  
  19. The DMSDOS filesystem was inspired by the THS filesystem (a simple doublespace
  20. DS-0-2 compressed read-only filesystem) written 1994 by Thomas Scheuermann.
  21.  
  22. The DMSDOS filesystem is distributed under the Gnu General Public Licence.
  23. See file COPYING for details.
  24. ******************************************************************************
  25.  
  26. */
  27.  
  28. #include <linux/fs.h>
  29. #include <linux/errno.h>
  30. #include <linux/kernel.h>
  31. #include <linux/msdos_fs.h>
  32. #include <linux/dmsdos_fs.h>
  33. #include <linux/string.h>
  34. #include <linux/sched.h>
  35.  
  36. extern Dblsb dblsb[];
  37.  
  38. #define NEAR_AREA 512
  39. /* no change for doublespace, but fixes drivespace 3 problems (was 50) */
  40. #define BIG_HOLE (dblsb[cvfnr].s_sectperclust*3+2) 
  41.  
  42. struct wait_queue * alloc_wait = NULL;
  43. int alloc_lock=0;
  44. void lock_alloc(void)
  45. { while(alloc_lock)sleep_on(&alloc_wait);
  46.   alloc_lock=1;
  47. }
  48. void unlock_alloc(void)
  49. { alloc_lock=0;
  50.   wake_up(&alloc_wait);
  51. }
  52.  
  53. struct wait_queue * readwrite_wait = NULL;
  54. int readwrite_lock=0;
  55. void lock_readwrite(void)
  56. { while(readwrite_lock)sleep_on(&readwrite_wait);
  57.   readwrite_lock=1;
  58. }
  59. void unlock_readwrite(void)
  60. { readwrite_lock=0;
  61.   wake_up(&readwrite_wait);
  62. }
  63.  
  64. void free_chain(struct super_block*sb, int clusternr, int cvfnr)
  65. { 
  66.   Mdfat_entry mde,dummy,newmde;
  67.   int newval=0;
  68.   int i;
  69.   int sektors;
  70.   int sektornr;
  71.   int merk;
  72.   
  73.   lock_alloc();
  74.   while(clusternr>0)
  75.   { /*printk("DMSDOS: free chain: freeing cluster %d\n",clusternr);*/
  76.     /* read mdfat entry and clear */
  77.     newmde.sector_minus_1=0;
  78.     newmde.size_lo_minus_1=0;
  79.     newmde.size_hi_minus_1=0;
  80.     newmde.flags=0;
  81.     dbl_mdfat_value(sb,clusternr,cvfnr,NULL,&mde);
  82.     dbl_mdfat_value(sb,clusternr,cvfnr,&newmde,&dummy);
  83.     sektors=mde.size_lo_minus_1+1;
  84.     sektornr=mde.sector_minus_1+1;
  85.     if(mde.flags&2)
  86.     {
  87.       /* free sectors in bitfat */
  88.       for(i=0;i<sektors;++i)dbl_bitfat_value(sb,sektornr+i,cvfnr,&newval);
  89.       dblsb[cvfnr].s_full=0;
  90.     }
  91.     else
  92.     { printk("DMSDOS: CVF %d: invalid MDFAT entry for cluster %d, zeroing it - check filesystem\n",
  93.              cvfnr+1,clusternr);
  94.     }
  95.     /* read fat entry and clear */
  96.     merk=clusternr;
  97.     clusternr=dbl_fat_nextcluster(sb,clusternr,cvfnr,NULL);
  98.     dbl_fat_nextcluster(sb,merk,cvfnr,&newval);
  99.   }
  100.   unlock_alloc();
  101. }
  102.  
  103. int find_free_bitfat(struct super_block*sb, int sektornr,int cvfnr, int size)
  104. { int testsek;
  105.   int i;
  106.  
  107.   if(sektornr>=dblsb[cvfnr].s_datastart&&sektornr<=dblsb[cvfnr].s_dataend-size)
  108.   { /* search exactly fitting hole near sektornr */
  109.     testsek=sektornr;  
  110.     while(testsek<sektornr+NEAR_AREA)
  111.     { if(dbl_bitfat_value(sb,testsek,cvfnr,NULL))
  112.       { ++testsek;
  113.         continue;
  114.       }
  115.       i=1;
  116.       while(i<=size&&dbl_bitfat_value(sb,testsek+i,cvfnr,NULL)==0)++i;
  117.       if(i==size)
  118.       { dblsb[cvfnr].s_full=0; 
  119.         return testsek;
  120.       }
  121.       testsek+=i;
  122.     }
  123.     testsek=sektornr;
  124.     while(testsek>sektornr-NEAR_AREA)
  125.     { if(dbl_bitfat_value(sb,testsek,cvfnr,NULL))
  126.       { --testsek;
  127.         continue;
  128.       }
  129.       i=1;
  130.       while(i<=size&&dbl_bitfat_value(sb,testsek-i,cvfnr,NULL)==0)++i;
  131.       if(i==size)
  132.       { dblsb[cvfnr].s_full=0;
  133.         return testsek-i+1;
  134.       }
  135.       testsek-=i;
  136.     }
  137.   }
  138.   
  139.   /* search for a big hole */
  140.   testsek=dblsb[cvfnr].s_datastart;
  141.   while(testsek<=dblsb[cvfnr].s_dataend-size)
  142.   { if(dbl_bitfat_value(sb,testsek,cvfnr,NULL))
  143.     { ++testsek;
  144.       continue;
  145.     }
  146.     i=1;
  147.     while(i<BIG_HOLE&&dbl_bitfat_value(sb,testsek+i,cvfnr,NULL)==0)++i;
  148.     if(i==BIG_HOLE)
  149.     { dblsb[cvfnr].s_full=0;
  150.       return testsek;
  151.     }
  152.     testsek+=i;
  153.   }
  154.   
  155.   /* search for an exactly fitting hole */
  156.   testsek=dblsb[cvfnr].s_datastart;
  157.   while(testsek<=dblsb[cvfnr].s_dataend-size)
  158.   { if(dbl_bitfat_value(sb,testsek,cvfnr,NULL))
  159.     { ++testsek;
  160.       continue;
  161.     }
  162.     i=1;
  163.     while(i<=size&&dbl_bitfat_value(sb,testsek+i,cvfnr,NULL)==0)++i;
  164.     if(i==size)
  165.     { dblsb[cvfnr].s_full=0;
  166.       return testsek;
  167.     }
  168.     testsek+=i;
  169.   }
  170.   
  171.   if(dblsb[cvfnr].s_full==0)
  172.   printk(KERN_EMERG "DMSDOS: CVF %d almost full or highly fragmented at MDFAT level, refusing further non-root write access.\n",
  173.          cvfnr+1);
  174.   
  175.   dblsb[cvfnr].s_full=1;
  176.   /* last trial: search for any hole >= size */
  177.   testsek=dblsb[cvfnr].s_datastart;
  178.   while(testsek<=dblsb[cvfnr].s_dataend-size)
  179.   { if(dbl_bitfat_value(sb,testsek,cvfnr,NULL))
  180.     { ++testsek;
  181.       continue;
  182.     }
  183.     i=1;
  184.     while(i<size&&dbl_bitfat_value(sb,testsek+i,cvfnr,NULL)==0)++i;
  185.     if(i==size)return testsek;
  186.     testsek+=i;
  187.   }
  188.   
  189.   /* not found, means disk full or MDFAT too fragmented */
  190.   dblsb[cvfnr].s_full=2;
  191.   printk(KERN_EMERG "DMSDOS: CVF %d full or too fragmented at MDFAT level - see doc\n",cvfnr+1);
  192.   return 0;
  193. }
  194.  
  195. /* finds a free cluster, marks it as end in fat,
  196.    returns clusternr 
  197.    returns -ENOSPC if disk full 
  198.    
  199.    **** do not call directly, call the user preferable allocation functions
  200.         instead
  201. */
  202. int allocate_cluster(struct super_block*sb, int cvfnr)
  203. { 
  204.   int i;
  205.   int newval;
  206.   int clusternr;
  207.   Mdfat_entry mde;
  208.   
  209.   /* when filesystem is almost full, only root may use the last BIG_HOLE
  210.      sectors since it can be dangerous to fill a CVF upto its neck 
  211.      - so ignore the s_full flag on root */
  212.   if(dblsb[cvfnr].s_full!=0&¤t->euid!=0)return -ENOSPC;
  213.   
  214.   /* if there's *really* nothing free any more, don't let root write */
  215.   if(dblsb[cvfnr].s_full==2)return -ENOSPC;
  216.   
  217.   /* find free cluster in fat */
  218.   clusternr=0;
  219.   for(i=2;i<=dblsb[cvfnr].s_max_cluster;++i)
  220.   { if(dbl_fat_nextcluster(sb,i,cvfnr,NULL)==0)
  221.     { clusternr=i;
  222.  
  223.       /* check mdfat if empty */
  224.       dbl_mdfat_value(sb,clusternr,cvfnr,NULL,&mde);
  225.       if(mde.flags&2)
  226.       { printk("DMSDOS: CVF %d: MDFAT contradicts FAT for cluster %d, ignoring entry - check filesystem!\n",
  227.                cvfnr+1,clusternr);
  228.       }
  229.       else
  230.       {
  231.         /* okay, mark appended cluster as 'end' */
  232.         newval=0xFFFF;
  233.         dbl_fat_nextcluster(sb,clusternr,cvfnr,&newval);
  234.         
  235.         return clusternr;
  236.       }
  237.     }
  238.   }
  239.   
  240.   return -ENOSPC;
  241. }
  242.  
  243. /* user preferable cluster allocation routines */
  244.  
  245. int allocate_first_cluster(struct super_block*sb, int cvfnr)
  246. { int res;
  247.  
  248.   lock_alloc(); 
  249.   res=allocate_cluster(sb,cvfnr);
  250.   unlock_alloc();
  251.   return res;
  252. }
  253.  
  254. int allocate_next_cluster(struct super_block*sb, int akt_cluster, int cvfnr)
  255. { 
  256.   int res;
  257.  
  258.   lock_alloc();
  259.   res=allocate_cluster(sb,cvfnr);
  260.   if(res>0)dbl_fat_nextcluster(sb,akt_cluster,cvfnr,&res);
  261.   unlock_alloc();
  262.   return res;
  263. }
  264.  
  265. /* replaces an existing cluster;
  266.    this unusual function must be called before rewriting any file cluster;
  267.    *** size must be known (encoded in mde) ***
  268.    it does nothing if called too often;
  269.    returns first sector nr
  270. */
  271.  
  272. int replace_existing_cluster(struct super_block*sb, int cluster, 
  273.                              int near_sector,
  274.                              Mdfat_entry*mde, int cvfnr)
  275. { Mdfat_entry old_mde,new_mde,dummy;
  276.   int i;
  277.   int newval;
  278.   int sektor;
  279.   int old_sektor;
  280.   int old_size;
  281.   int new_size;
  282.   
  283.   lock_alloc();
  284.  
  285.   /* printk("DMSDOS: replace_existing_cluster cluster=%d near_sector=%d mdfatbits=0x%x cvfnr=%d\n",
  286.          cluster,near_sector,mdfatbits,cvfnr+1);*/
  287.   dbl_mdfat_value(sb,cluster,cvfnr,NULL,&old_mde);
  288.   old_size=old_mde.size_lo_minus_1+1;
  289.   old_sektor=old_mde.sector_minus_1+1;
  290.   new_size=mde->size_lo_minus_1+1;
  291.   if(old_mde.flags&2)
  292.   {
  293.     /* test whether same length */
  294.     if(old_size==new_size)
  295.     { /*printk("DMSDOS: replace_existing_cluster: same length, ok\n");*/
  296.       sektor=old_sektor;
  297.       goto mdfat_update;
  298.     }
  299.     /* different length, replace mdfat entry */
  300.     newval=0;
  301.     /*printk("DMSDOS: replace_existing_cluster: freeing old sectors...\n");*/
  302.     for(i=0;i<old_size;++i)dbl_bitfat_value(sb,old_sektor+i,cvfnr,&newval);
  303.     /*printk("DMSDOS: replace_existing_cluster: freeing finished\n");*/
  304.   }
  305.   /*printk("DMSDOS: replace_existing_cluster: call find_free_bitfat...\n");*/
  306.   sektor=find_free_bitfat(sb,near_sector,cvfnr,new_size);
  307.   /*printk("DMSDOS: replace_existing_cluster: find_free_bitfat returned %d\n",
  308.          sektor);*/
  309.   if(sektor==0)
  310.   { if(old_mde.flags&2)
  311.     {
  312.       /* undo bitfat free */
  313.       newval=1;
  314.       for(i=0;i<old_size;++i)dbl_bitfat_value(sb,old_sektor+i,cvfnr,&newval);
  315.     }
  316.     unlock_alloc();
  317.     return -ENOSPC; /* disk full */
  318.   }
  319.   /* check whether really free (bug supposed in find_free_bitfat) */
  320.   for(i=0;i<new_size;++i)
  321.   { if(dbl_bitfat_value(sb,sektor+i,cvfnr,NULL))
  322.     { printk(KERN_EMERG "DMSDOS: find_free_bitfat returned sektor %d size %d but they are not all free!\n",
  323.              sektor,new_size);
  324.       unlock_alloc();
  325.       panic("This is a dmsdos bug - reboot and check filesystem\n");
  326.       return -EIO;
  327.     }
  328.   }
  329.   newval=1;
  330.   /*printk("DMSDOS: replace_existing_cluster: allocating in bitfat...\n");*/
  331.   for(i=0;i<new_size;++i)dbl_bitfat_value(sb,sektor+i,cvfnr,&newval);
  332.   
  333. mdfat_update:
  334.   new_mde.sector_minus_1=sektor-1;
  335.   new_mde.size_lo_minus_1=mde->size_lo_minus_1;
  336.   new_mde.size_hi_minus_1=mde->size_hi_minus_1;
  337.   new_mde.flags=mde->flags|2;
  338.   /*printk("DMSDOS: replace_existing_cluster: writing mdfat...\n");*/
  339.   dbl_mdfat_value(sb,cluster,cvfnr,&new_mde,&dummy);
  340.   unlock_alloc();
  341.   return sektor; /* okay */
  342. }
  343.  
  344. /* user preferable cluster allocation functions for directories */
  345. /* cluster is uncompressed, of maximum size and zerod out and written */
  346.  
  347. int allocate_first_dir_cluster(struct super_block*sb,int cvfnr)
  348. { int res;
  349.   int sektor;
  350.   int cluster;
  351.   int i;
  352.   int size;
  353.   struct buffer_head*bh;
  354.   int newval;
  355.   Mdfat_entry mde;
  356.   
  357.   res=allocate_first_cluster(sb,cvfnr);
  358.   if(res<=0)return res;
  359.   cluster=res;
  360.   size=dblsb[cvfnr].s_sectperclust;
  361.   mde.size_lo_minus_1=size-1;
  362.   mde.size_hi_minus_1=size-1;
  363.   mde.flags=3;
  364.   res=replace_existing_cluster(sb,cluster,0,&mde,cvfnr);
  365.   if(res<0)
  366.   { /* undo cluster allocation */
  367.     newval=0;
  368.     dbl_fat_nextcluster(sb,cluster,cvfnr,&newval); 
  369.     return res;
  370.   }
  371.   
  372.   /* zero it out since it is an empty dir cluster */
  373.   sektor=res;
  374.   for(i=0;i<size;++i)
  375.   { bh=noread_dbl_sector(sb,sektor+i,cvfnr);
  376.     if(bh==NULL)
  377.     { /* undo cluster allocation */
  378.       newval=0;
  379.       dbl_fat_nextcluster(sb,cluster,cvfnr,&newval);
  380.       return -EIO;
  381.     }
  382.     memset(bh->b_data,0,SECTOR_SIZE);
  383.     bh_dirty(sb,bh);
  384.     bh_free(sb,bh);
  385.   }
  386.   
  387.   return cluster;
  388. }
  389.  
  390. int allocate_next_dir_cluster(struct super_block*sb, int akt_cluster,
  391.                               int cvfnr)
  392. { int res;
  393.   int sektor;
  394.   int i;
  395.   struct buffer_head*bh;
  396.   int cluster;
  397.   int size;
  398.   int newval;
  399.   Mdfat_entry mde;
  400.   
  401.   res=allocate_next_cluster(sb,akt_cluster,cvfnr);
  402.   if(res<=0)return res;
  403.   cluster=res;
  404.   size=dblsb[cvfnr].s_sectperclust;
  405.   mde.size_lo_minus_1=size-1;
  406.   mde.size_hi_minus_1=size-1;
  407.   mde.flags=3;
  408.   sektor=dbl_mdfat_cluster2sector(sb,akt_cluster,cvfnr);
  409.   res=replace_existing_cluster(sb,cluster,sektor,&mde,cvfnr);
  410.   if(res<0)
  411.   { /* undo cluster allocation */
  412.     newval=0;
  413.     dbl_fat_nextcluster(sb,cluster,cvfnr,&newval);
  414.     newval=-1;
  415.     dbl_fat_nextcluster(sb,akt_cluster,cvfnr,&newval);
  416.     return res;
  417.   }
  418.   
  419.   /* zero it out since it is an empty dir cluster */
  420.   sektor=res;
  421.   for(i=0;i<size;++i)
  422.   { bh=noread_dbl_sector(sb,sektor+i,cvfnr);
  423.     if(bh==NULL)
  424.     { /* undo cluster allocation */
  425.       newval=0;
  426.       dbl_fat_nextcluster(sb,cluster,cvfnr,&newval);
  427.       newval=-1; /* cut off or directory will be unreadable */
  428.       dbl_fat_nextcluster(sb,akt_cluster,cvfnr,&newval);
  429.       return -EIO;
  430.     }
  431.     memset(bh->b_data,0,SECTOR_SIZE);
  432.     bh_dirty(sb,bh);
  433.     bh_free(sb,bh);
  434.   }
  435.   
  436.   return cluster;
  437. }
  438.  
  439. int scan_dbl_dir_4_empty(struct super_block*sb, int dirstartclust, int cvfnr)
  440. {  return scan_dbl_dir_4_n_empty(sb,dirstartclust,cvfnr,1,NULL);
  441. }
  442.  
  443. /* find n empty dir entries
  444.    append a dir cluster if necessary
  445.    fills lfn_inos if !=NULL
  446. */
  447.  
  448. int scan_dbl_dir_4_n_empty(struct super_block*sb, int dirstartclust, int cvfnr,
  449.                            int n,int*lfn_inos)
  450. { int ino;
  451.   int ent=0;
  452.   unsigned char buf[32];
  453.   int lastcluster;
  454.   int merk;
  455.   struct inode * inode;
  456.   int found=0;
  457.   
  458.   /* fill first unused with zero -- for safety */
  459.   if(lfn_inos)lfn_inos[n]=0;
  460.   
  461.   while((ino=read_dbl_direntry(sb,dirstartclust,cvfnr,ent,buf))>0)
  462.   { ++ent;
  463.     if(buf[0]==0xe5||buf[0]==0)
  464.     {  inode=iget(sb,ino);
  465.        if(MSDOS_I(inode)->i_busy==0)
  466.        { iput(inode);
  467.          ++found;
  468.          if(lfn_inos)lfn_inos[n-found]=ino;
  469.          if(n==found)return ino;
  470.        }
  471.        else
  472.        { found=0;
  473.          iput(inode);
  474.        }
  475.     }
  476.     else found=0;
  477.     
  478.   }
  479.   if(dirstartclust==0)return -ENOSPC; /* root dir full */
  480.   
  481.   if(ent%(dblsb[cvfnr].s_sectperclust*16))
  482.   { printk("DMSDOS: scan_dbl_dir_4_empty: scan error occured, refusing to append cluster\n");
  483.     return -ENOSPC;
  484.   }
  485.   
  486.   /* okay, must append a cluster */
  487.   lastcluster=dirstartclust;
  488.   while((merk=dbl_fat_nextcluster(sb,lastcluster,cvfnr,NULL))>0)
  489.                                                          lastcluster=merk;
  490.   lastcluster=allocate_next_dir_cluster(sb,lastcluster,cvfnr);
  491.   if(lastcluster<0) return -ENOSPC; /* disk full */
  492.   /* the cluster is already zerod out */
  493.   
  494.   while(found<n)
  495.   {
  496.     ino=read_dbl_direntry(sb,dirstartclust,cvfnr,ent,buf);
  497.     if(ino<0)
  498.     { printk("DMSDOS: scan_dbl_dir_4_empty: error after appending dir cluster\n");
  499.       return ino;
  500.     }
  501.     ++found;++ent;
  502.     if(lfn_inos)lfn_inos[n-found]=ino;
  503.   }
  504.   return ino;
  505. }
  506.  
  507. int moveback(struct super_block*sb, int clusternr, int cvfnr)
  508. { Mdfat_entry mde,dummy;
  509.   int sector;
  510.   int i,newval;
  511.   struct buffer_head*bh1,*bh2;
  512.   
  513.   if(clusternr<2||clusternr>dblsb[cvfnr].s_max_cluster)return -EINVAL;
  514.  
  515.   lock_alloc();
  516.   
  517.   dbl_mdfat_value(sb,clusternr,cvfnr,NULL,&mde);
  518.   if(mde.flags&2) /* used */
  519.   { sector=mde.sector_minus_1;
  520.     if(dbl_bitfat_value(sb,sector,cvfnr,NULL)==0)
  521.     { while(dbl_bitfat_value(sb,sector-1,cvfnr,NULL)==0)--sector;
  522.       /* copy cluster */
  523.       /* printk("DMSDOS: moving cluster %d from sector %ld to %d\n",clusternr,
  524.              mde.sector_minus_1+1,sector);*/
  525.       for(i=0;i<=mde.size_lo_minus_1;++i)
  526.       { bh1=read_dbl_sector(sb,mde.sector_minus_1+1+i,cvfnr);
  527.         if(bh1==NULL) goto err_out;
  528.         bh2=noread_dbl_sector(sb,sector+i,cvfnr);
  529.         if(bh2==NULL)
  530.         { bh_free(sb,bh1);
  531.         err_out:
  532.           unlock_alloc();
  533.           printk("DMSDOS: moveback failed (couldn't read data)!\n");
  534.           return -EIO;
  535.         }
  536.         memcpy(bh2->b_data,bh1->b_data,SECTOR_SIZE);
  537.         bh_dirty(sb,bh2);
  538.         bh_free(sb,bh1);
  539.         bh_free(sb,bh2);
  540.       }
  541.       /* free in bitfat */
  542.       newval=0;
  543.       for(i=0;i<=mde.size_lo_minus_1;++i)
  544.            dbl_bitfat_value(sb,mde.sector_minus_1+1+i,cvfnr,&newval);
  545.       /* allocate in bitfat */
  546.       newval=1;
  547.       for(i=0;i<=mde.size_lo_minus_1;++i)
  548.            dbl_bitfat_value(sb,sector+i,cvfnr,&newval);
  549.       /* save in mdfat */
  550.       mde.sector_minus_1=sector-1;
  551.       dbl_mdfat_value(sb,clusternr,cvfnr,&mde,&dummy);                                                    
  552.     }
  553.   }
  554.   
  555.   unlock_alloc();
  556.   return 0;
  557. }